3MENTAL, un Modelo Computacional Universal

MENTAL, UN MODELO
COMPUTACIONAL
UNIVERSAL

“Es posible inventar una sola máquina que pueda ser utilizada para calcular cualquier secuencia computable” (Alan Turing)

“Todo algoritmo o procedimiento efectivo es computable por una máquina de Turing” (Tesis Church-Turing)

“El modelo computacional es la realidad, no un medio para estudiarla” (Heinz Pagels)

Computación, Algoritmo y Modelos Computacionales
Computación vs. Algoritmo

En primer lugar, hay que diferenciar entre computación y algoritmo:

Una computación es la evaluación de una expresión. El resultado de la evaluación es el resultado de la computación. La computación es secuencial, fija, ciega, mecánica, inconsciente. Por ejemplo, el cálculo de una expresión aritmética.

El término “computación” no va necesariamente asociado a expresiones numéricas. La raíz etimológica de “computación” viene del latín del prefijo “com” (al mismo tiempo) y “putare” (contemplar o evaluar), es decir contemplar o evaluar cosas al mismo tiempo.
Un algoritmo es un proceso orientado a obtener un resultado final. En este proceso hay también computaciones e incluye cierto razonamiento o lógica de decisión. Un algoritmo, en este sentido es más general que una computación. Ejemplos: un algoritmo que determina si un número natural es o no primo; el algoritmo de Euclides de cálculo del máximo común divisor; el algoritmo que encuentra el máximo de un conjunto de números.

Una computación es un caso particular de algoritmo cuando no hay lógica o razonamiento. No obstante, frecuentemente, computación y algoritmo se consideran equivalentes. Ambos conceptos tienen en común el ser determinísticos.

Ambos conceptos (computación y algoritmo) son difíciles de definir de forma precisa, por lo que se acude a los denominados “modelos computacionales”, que son formalismos generales que permiten implementar computaciones y algoritmos concretos. Estos modelos son tesis, es decir, no son demostrables porque se establecen como fundamento.

El cálculo lambda de Church

El primero en proponer un modelo computacional fue Alonzo Church, en 1936, mediante el llamado “cálculo lambda” (lambda calculus), un cálculo de tipo funcional y recursivo para formalizar las funciones computables. Este sistema, que incluía un lenguaje formal, proponía un modelo basado en expresiones funcionales, que son funciones definidas a partir de otras funciones. La tesis de Church era: “Una función de enteros positivos es efectivamente calculable solo si es recursiva”.

Cuando se inventó el cálculo lambda, los ordenadores todavía no existían. Sin embargo, se puede considerar el primer lenguaje funcional de la historia. Posteriormente ha constituido el fundamento de muchos lenguajes funcionales, habiendo tenido también gran influencia en el diseño de los lenguajes de programación en general.

El propósito original de Church era construir un sistema formal para toda la matemática, pero para evitar que aparecieran paradojas (como la de Russell) al construir expresiones autorreferenciales, separó el cálculo lambda y lo utilizó para formalizar la computabilidad.

La máquina de Turing

Pocos meses después de que Church hiciera público su modelo funcional, Alan Turing propuso (sin tener conocimiento de la propuesta de Church) un modelo alternativo, aún más simple: un dispositivo teórico que hoy denominamos “máquina de Turing”, basada en unas pocas operaciones básicas que permitían implementar cualquier algoritmo. En este caso, no había un lenguaje formal.

Posteriormente se inventaron otros modelos de computación para implementar la noción de algoritmo, como las funciones recursivas parciales de Gödel, los algoritmos de Markov y la máquina de Post.

Todos estos modelos, aunque aparentemente diferentes, han demostrado ser equivalentes. Esto ha conducido a la aceptación universal de lo que se conoce como tesis de Church-Turing: el concepto intuitivo de algoritmo puede ser implementado mediante una máquina de Turing o mediante las funciones recursivas del cálculo lambda. Ambos enfoques (operativo y funcional, respectivamente) delimitan el máximo poder computacional posible. Todo algoritmo que se pueda describir mediante el cálculo lambda puede describirse también mediante una máquina de Turing, y viceversa. La tesis de Church-Turing es considerada como la ley fundamental de la computación.

Turing, en su famoso artículo de 1936 “On Computable Numbers, with an Application to the Entscheidungsproblem” (publicado en la revista “Proceedings of the London Mathematical Society) ideó un dispositivo teórico universal para implementar algoritmos. Este modelo se convirtió en el modelo estándar de computación, el más popular y paradigmático por ser el más simple e intuitivo y ofrecer una imagen que enlazaba la computación teórica con un dispositivo físico abstracto. Este modelo, además, ha sido el inspirador de la arquitectura de los ordenadores.

Los conceptos en los que se basa esta máquina teórica son extraordinariamente simples:

Un espacio de memoria lineal (cinta), compuesta por una secuencia infinita de celdas numeradas. “Infinita” hay que interpretarlo como “ilimitada”, en el sentido de que al principio la cinta es finita y se van añadiendo celdas a medida que se necesitan.
Un conjunto finito de símbolos de un alfabeto.
Un conjunto finito de estados posibles de la máquina.
Una cabeza lectora/grabadora (o cabezal) de símbolos de un alfabeto sobre la cinta. Inicialmente la cinta finita tiene blancos y las celdas que se van añadiendo contienen también blancos.
Un conjunto de reglas (también finito) del tipo “condición → acción”. Las reglas son de la forma (E₁, S₁ → S₂, M, E₂), con 2 condiciones y 3 acciones:

Observaciones:

La parada de la máquina se produce cuando no hay ninguna regla que pueda aplicarse. Se supone que cuando la máquina de Turing se para es porque ha obtenido el resultado. Si no se para, es que no es posible alcanzar un resultado final.
El resultado se obtiene sobre la propia cinta, puesto que es la única memoria disponible.
Se supone que un agente (mecánico o humano) examina las reglas y las ejecuta.
Los símbolos se pueden reducir a ceros y unos, puesto que todo alfabeto finito se puede codificar mediante dígitos binarios.
El movimiento del cabezal es relativo a la cinta. Da la mismo que lo que se desplace sea la cinta o el cabezal.

La máquina de Turing universal

La máquina de Turing universal (MTU) es una meta-máquina, una máquina de máquinas, una máquina general que puede simular cualquier máquina de Turing particular. Es una máquina de Turing que contiene al principio de la cinta la codificación de una máquina de Turing particular basada en la tabla de reglas (condiciones − acciones), reglas que se pueden codificar mediante los valores asociados a las condiciones y a las acciones. Por ejemplo:

Condiciones		Acciones
Estado actual	Símbolo leído	Símbolo a grabar	Mov. cabeza	Nuevo estado
1	a	c	Derecha	2
2	b	a	Izquierda	3
3	c	b	Derecha	1

La notable aportación de Turing

Turing, en su famoso artículo de 1936 logró varias cosas:

Que existen unos principios simples subyacentes en toda computación y que se reducen, en definitiva, a una mera manipulación de símbolos mediante la aplicación de una serie de reglas formales simples.
Inventó un dispositivo teórico para formalizar los concepto de computación y algoritmo. De esta forma, conectó matemática (computación) con dispositivos mecánicos (o autómatas).
Inventó un dispositivo universal de computación, la máquina de Turing Universal (MTU). El código almacenado en la memoria hace flexible el dispositivo y lo convierte en universal, en un dispositivo de propósito general. Los computadores actuales son implementaciones, en términos generales, la MTU y el origen de la arquitectura von Neumann, un ordenador con programa almacenado en memoria.
Demostró que hay números irracionales incomputables. Como el conjunto de todos los posibles programas es numerable, el conjunto de los números reales computables también lo es. Como el conjunto de los números reales no es numerable (como demostró Cantor), hay números reales que no son computables. Como los números reales no numerables son la mayoría de los números reales, la mayoría de los números reales son incomputables.

Un número computable es un número real que puede ser calculado con la precisión que se desee mediante un algoritmo en un número finito de pasos.

Además, con la MTU es posible modificar el programa durante su ejecución.
Demostró que el problema de la parada (halting problem) es indecidible, es decir, no es posible saber si una máquina de Turing se parará o no. El problema de la parada de una máquina de Turing equivalente al problema de decidibilidad de Hilbert [ver Adenda.]
Aportó un nuevo enfoque al teorema de la incompletud de Gödel al establecer una analogía entre demostración y computación. De la misma manera que hay proposiciones matemáticas indecidibles (no demostrables) a partir de un conjunto de axiomas, hay números que no son computables (mediante un procedimiento finito y en un tiempo finito) mediante las operaciones básicas de una máquina de Turing.

Limitaciones de la máquina de Turing

A pesar de las virtudes de la máquina de Turing, existen muchas limitaciones que cuestionan seriamente la validez o utilidad de este modelo computacional, limitaciones que apuntan la necesidad de sustituirlo por otro más general y completo.

No entorno.
La máquina de Turing no tiene entorno. Es un sistema cerrado, sin comunicación con el exterior.
No interactividad.
Al no tener entorno, no es posible la interactividad con otros agentes (usuarios u otras máquinas de Turing). Solo se pueden implementar algoritmos deterministas. El comportamiento de la máquina está determinado a partir de la entrada.

Wegner [1997, 1999] y Stein [1999] han propuesto como nuevo paradigma de computación la “computación interactiva”. Sostienen que la interacción es un concepto más potente que el de algoritmo, pues no puede implementarse sobre una máquina de Turing, y que toda computación se puede modelar como interacción. El método Wegner-Stein describe el cálculo como interacción y ofrece un modelo para la programación orientada a eventos. Esto está en contraposición con la famosa tesis de Church-Turing, que afirma que “todo aquello que se puede computar se puede implementar en una máquina de Turing”.
No dispositivos de entrada/salida.
No hay dispositivos de entrada ni de salida. La entrada y la salida están integradas en la única cinta, donde también se almacenan los resultados intermedios.
Parada de la máquina.
No existe una acción específica para parar la máquina. La máquina se para cuando no hay ninguna regla que pueda aplicarse. Pero hay procesos que siempre están activos como son los sistemas operativos.
Código no modificable.
En una máquina de Turing el código no es modificable porque el código no está en la cinta, sino solo los datos (fijos) asociados a las reglas.
Estructura de datos.
La única estructura de datos es la cinta, que es de tipo lineal.
Nivel de abstracción.
El nivel de abstracción es muy bajo porque el código está restringido a reglas. Programar un algoritmo requiere mucho detalle, por lo que es una labor muy tediosa. No se pueden especificar estructuras de información de mayor nivel de abstracción como expresiones funcionales, eventos, objetos, etc. Tampoco se pueden utilizar variables para almacenar resultados intermedios.
Modelo incompleto.
El modelo es solo computacional. No es descriptivo.
No paralelismo.
La máquina de Turing no admite paralelismo. Todas las operaciones se ejecutan en secuencia. Tampoco soporta paralelismo de datos (de entrada, de salida o internos).
No lenguaje formal.
No existe un lenguaje formal asociado a este modelo de computación. Se suele recurrir a pseudocódigo o al lenguaje natural.
Paradigma.
La máquina de Turing implementa solo el paradigma imperativo. No permite implementar paradigmas de mayor nivel de abstracción (lógico, funcional, relacional, objetual, etc.).
Localidad.
La máquina de Turing es un dispositivo local. Para acceder desde una posición de la cinta a otra, el cabezal tiene que recorrer todas las posiciones intermedias.
No reflexividad.
No hay reglas de orden superior (reglas de reglas). Como no es multiparadigma, no hay funciones de orden superior (metafunciones), datos de datos (metadatos), etc.

La máquina de Turing es reconocida como una idea brillante que dio origen a la idea de “ordenador de propósito general”. Pero hoy día la máquina de Turing es claramente insuficiente por las limitaciones señaladas.

El propio Turing ideó unas extensiones de su máquina teórica presentada en 1936. Las introdujo en su tesis doctoral de 1938 “Systems of Logic Based on Ordinals” [Turing, 1939]. [ver Adenda.]

Según la tesis de Church-Turing, la máquina de Turing representa no solo lo computable sino también los límites de lo computable. Todo algoritmo o procedimiento efectivo es computable por una máquina deTuring. Máquina de Turing y algoritmo han llegado a significar la misma cosa, pues la máquina de Turing ha conseguido concretar el concepto difuso de algoritmo como “procedimiento efectivo” de computación. En este sentido, la computación sería un tema absolutamente cerrado a otras alternativas de tipo lógico, matemático, físico o biológico.

Sin embargo, desde que apareció la máquina de Turing, se ha planteado repetidamente la cuestión de la existencia de un modelo computacional superior a la máquina de Turing. Es la cuestión de la hipercomputación (o computación super-Turing). A este cuestionamiento del modelo computacional de la máquina de Turing ha contribuido la física cuántica, que podría aportar un nuevo modelo computacional más avanzado debido a la posibilidad de proceso paralelo y su mayor capacidad de computación.

Hipercomputación y computación super-Turing no son exactamente sinónimos. Puesto que la máquina de Turing es físicamente realizable, la computación super-Turing se supone que es también físicamente realizable, mientras que en la hipercomputación no hay tal suposición; es un modelo teórico o abstracto.

En principio, la hipercomputación es adoptar un nuevo modelo teórico de computación que superase las limitaciones señaladas.

Lenguaje de programación esencial

Un lenguaje de programación esencial es un lenguaje con las características mínimas o esenciales para que sea capaz de expresar cualquier algoritmo. Se demuestra [Brookshear, 1993] que las características de dicho lenguaje de programación esencial son:

Tipo de datos: número entero no negativo.
Identificadores: nombres, cada uno de los cuales tiene asociado un valor.
Sentencias simples:
Estructura de control (sentencia compuesta):

Cualquier lenguaje de programación que tenga esta características mínimas tiene el máximo poder computacional conocido. Cualquier otra característica adicional no añade poder computacional alguno.

Algoritmo vs. Sistema interactivo

La tecnología de la computación ha evolucionado desde los modelos algorítmicos (deterministas) a los modelos interactivos (no deterministas). Esta evolución ha sido motivada por las limitaciones de los algoritmos:

La salida de un algoritmo está completamente determinada por la entrada, Todo algoritmo es determinista.
No tiene en cuenta el entorno, el cambiante mundo exterior. A la hora de computar son ciegos y mudos. No “ven” el entorno (para poder reaccionar o adaptarse a las circunstancias) ni “hablan” al entorno (no lo modifican).

Un sistema interactivo es una generalización de algoritmo en el sentido de que la interactividad no está orientado a buscar un resultado, sino que reacciona (interna y exteriormente) a los estímulos del entorno. Un algoritmo es un caso particular de sistema interactivo cuando no tiene estados internos ni se considera el entorno. Un sistema interactivo no sustituye al algoritmo, sino que es un grado de libertad adicional. Cuando no hay interactividad, tenemos el algoritmo tradicional, con una sola entrada, que realiza la computación y devuelve el resultado.

Los sistemas interactivos suministran un modelo o marco para inteligencia artificial, sistemas operativos, sistemas distribuidos, etc.

Por lo tanto, un sistema interactivo posee ventajas sobre el algoritmo:

Un sistema interactivo está abierto al mundo exterior a través del entorno. Los sistemas interactivos no son deterministas. Tienen un comportamiento flexible, pues tienen un estado interno y se adaptan a la situación del entorno con el que interactúan usuarios, agentes, procedimientos, etc.
Permite modelar situaciones o problemas de manera más simple, pues cuanto más genéricos sean los recursos computacionales, mayor es la libertad. El poder computacional está ligado al grado de libertad: cuanto más libertad y flexibilidad, más fácil es la solución de los problemas. Lo que antes era complejo se ve menos complejo o más fácil.
La forma más simple de modelar la interactividad es a través del entorno, en donde los datos de entrada y de salida residen en el entorno. Para que el propio sistema interactivo pueda auto-modificarse, también debe residir en el entorno.
Un sistema interactivo lo podemos considerar como un meta-algoritmo, un algoritmo de orden superior o general que está alerta al entorno y, en función de los valores del entorno, ejecuta diferentes algoritmos particulares. Estos algoritmos pueden modificar, a su vez, el entorno como respuesta.
Un sistema interactivo puede procesar eventos. Puede interrumpir el proceso en curso para atender la nueva situación del entorno. Incluso podría haber interrupciones de orden superior.

MENTAL: un Modelo Computacional Universal
MENTAL proporciona recursos computacionales que van más allá de una máquina de Turing. Es un modelo hipercomputacional (de tipo teórico) basado en expresiones construidas con las primitivas semánticas universales (o arquetipos primarios). Las expresiones pueden hacer uso de todos los recursos del lenguaje. En particular, una expresión puede tener la forma de un algoritmo, que es una expresión que contiene el comienzo y la finalización de la ejecución, con la devolución de un resultado.

MENTAL, un lenguaje de programación esencial

MENTAL cumple los requerimientos de un lenguaje de programación esencial y, por lo tanto, permite expresar cualquier problema que tenga una solución algorítmica:

N°	Lenguaje de programación esencial	MENTAL
1	Tipo de datos: entero no negativo.	Existe.
2	Identificadores: nombres, cada uno de los cuales tiene asociado un valor.	Pueden especificarse.
3	incr nombre; (incrementa en 1 el valor asociado a nombre)	`(nombre = nombre + 1)`
4	decr nombre; (decrementa en 1; si es cero, permanece dicho valor).	`( nombre>0 → (nombre = nombre − 1) )`
5	Estructura de control: While nombre ≠ 0 do; x End;	`⟨( (nombre ≠ 0) → x )⟩`

Características de MENTAL como modelo computacional

Modelo teórico.
El modelo computacional de MENTAL es un modelo teórico, como la máquina de Turing, pero es un modelo más abstracto y conceptual. No requiere de ningún referente físico, pues el modelo solo hace referencia a entidades abstractas.
Nivel de abstracción.
El nivel de abstracción de MENTAL es supremo, al basarse en arquetipos primarios.
Modelo universal.
MENTAL no es un modelo concreto de computación, de la misma manera que no es un lenguaje particular, ni un paradigma de programación particular, ni un modelo particular de la mente. Es la esencia de la computación, un modelo universal de computación basado en grados de libertad, que permite especificar modelos de computación particulares.

Los modelos computacionales de Turing y Church son solo aspectos o visiones particulares o superficiales del tema de la computación. La verdadera visión, la visión profunda y completa de la computación (y de la descripción) viene dada por los arquetipos primarios, de los que derivan todas las posibles expresiones.

MENTAL no es un modelo computacional más, sino un modelo unificador que sustituye al viejo modelo de Turing bajo nivel por otro de alto nivel, genérico, más conceptual, y que también ayude a comprender la naturaleza de la realidad interna y externa.

MENTAL es una tesis universal que sustituye a la tesis Church-Turing. La máquina de Turing no es apropiada como fundamento universal, ni siquiera para el mundo computacional. La máquina de Turing es un modelo computacional aceptado por la ciencia, pero se considera una teoría de la computación débil, primitiva y no evolucionada.

MENTAL es un lenguaje universal para las ciencias formales: matemática, informática, inteligencia artificial, etc.
Límites.
MENTAL establece los verdaderos límites de la computabilidad, que son los grados de libertad (las primitivas semánticas universales o arquetipos primarios) y sus posibilidades combinatorias.
Simplicidad.
Como modelo computacional universal, MENTAL permite implementar algoritmos conceptuales más simples y potentes.

Cuando Turing planteó la idea de una máquina universal tenía en mente el modelo computacional más simple posible que permitiera implementar todo tipo de algoritmos. De la misma manera, MENTAL es el lenguaje más simple posible, con el que se pueden crear todo tipo de expresiones y de donde emerge la complejidad. Cuanto más simple conceptualmente es un lenguaje, más posibilidades expresivas tiene.
Concepto de computación.
Con MENTAL el concepto se aclara y redefine el concepto de computación: la computación es todo proceso que pueda expresarse por combinación de las primitivas semánticas (dimensiones semánticas o grados de libertad). No hay leyes computacionales (como la tesis Church-Turing) sino solo grados de libertad o dimensiones semánticas.
Algorítmica semántica.
MENTAL proporciona un modelo computacional y una algorítmica de nueva generación, un nuevo tipo de algoritmos de base semántica, más flexibles, automodificables, inteligentes, con computación paralela, con “atajos computacionales”, capaz de manejar elementos descriptivos, etc. En definitiva, una algorítmica semántica, y que enlaza con la inteligencia artificial.
Entorno.
MENTAL posee entorno: el espacio abstracto. El código y los datos internos y externos residen en el entorno.
Interactividad.
MENTAL permite modelar la interactividad (y la gestión de eventos) a través del entorno, que es el medio universal de comunicación entre procesos y con agentes externos.
Código modificable.
MENTAL puede modificar su propio código, pues puede modificar cualquier tipo de estructura de información. El código es fácilmente modificable, pues reside en el entorno.
Código completo.
El código no está solo limitado a reglas sino que están disponibles todos los recursos del lenguaje.
Lenguaje formal.
MENTAL posee un lenguaje formal con el que se expresan y combinan las primitivas.
Modelo completo.
MENTAL es operativo y descriptivo. Lo descriptivo y lo operativo son dos aspectos del lenguaje.
Paralelismo.
MENTAL soporta paralelismo en general, que está soportado por la primitiva Conjunto (agrupación paralela), que es aplicable a datos o a procesos.
Estructuras de información.
MENTAL permite especificar todo tipo de estructuras de información pasiva (datos) y todo activas (funciones, procedimientos, objetos, reglas, etc.).
Reflexividad.
MENTAL permite especificar todo tipo de estructuras de orden superior (reglas de reglas, funciones de funciones, eventos de eventos, etc.).
Paradigmas.
MENTAL es un paradigma universal, capaz de implementar cualquier paradigma particular, incluyendo el paradigma imperativo de una máquina de Turing.
Modelo de la mente.
MENTAL, por su universalidad, proporciona un metamodelo de la mente porque no es un modelo concreto de la mente, sino un modelo universal basado en grados de libertad.

La tabla siguiente resume estas características diferenciadoras, en donde puede verse que el modelo computacional de la máquina de Turing es un modelo débil, y MENTAL es un modelo fuerte y completo. MENTAL es la realización del sueño de Church de crear un lenguaje o sistema formal para la matemática.

Característica	Máquina de Turing	MENTAL
Modelo teórico	Sí	Sí
Nivel de abstracción	Bajo	Supremo
Modelo	Particular	Universal
Límites	Tesis Chuch-Turing	Grados de libertad
Simplicidad	Sí (operativo)	Sí (conceptual)
Computación	Elemental	General
Algorítmica	Elemental	Semántica
Entorno	No	Sí (espacio abstracto)
Interactividad	No	Sí
Código modificable	No	Sí
Lenguaje formal	No	Sí
Tipo de modelo	Operativo	Operativo y descriptivo
Paralelismo	No	Sí
Estructuras de información	Limitadas	Las de las primitivas
Reflexividad	No	Sí
Paradigmas	Imperativo	Universal
Modelo de la mente	No	Sí (universal)

Especificación de una máquina de Turing en MENTAL

Cinta inicial:

(b = " ") // carácter blanco (cinta =: b★) // secuencia infinita de caracteres en blanco
Alfabeto:

(a0 = b) // carácter blanco (alfa = ( a0 … an )) // alfabeto de n caracteres

El alfabeto es el conjunto finito de elementos, símbolos o caracteres que pueden “grabarse” sobre la cinta.
Estados:

Hay m estados: 1, … , m.
Variables.

i: Número de posición del cabezal sobre la cinta. Inicialmente, (i = i0).

j: Número del estado. Inicialmente, (j = j0).

k: Número del elemento del alfabeto a grabar sobre la cinta en la posición del cabezal.
Acciones.
1. Desplazar el cabezal a la derecha: (i = i+1).
2. Desplazar el cabezal a la izquierda: (i = i−1).
3. Grabar el elemento de índice k en la actual posición (i) del cabezal sobre la cinta.
  
  (cinta\i = alfa\k)
4. Cambiar a estado j1: (j = j1)
5. Pararse: ¡ (finalizar la ejecución)
  Esta acción no la tiene la máquina de Turing, pero es muy útil incluirla porque permite detener la máquina de forma explícita.
Reglas.

La descripción del funcionamiento de la máquina se realiza mediante reglas del tipo:

⟨( (j = j1) → (cinta\i = alfa\k) → acciones )⟩

Es decir, si el estado es j1 y si en la actual posición de la cinta está el elemento del alfabeto de orden k, entonces ejecutar una o varias acciones. Hay dos condiciones (puede haber una condición o ninguna) y una o varias acciones entre las cinco alternativas mencionadas.
Forma general de una máquina de Turing:

( turing = ( (b = " ") (cinta =: b★) (a0 = b) (alfa = ( a0…an )) (i = i0) (j°> = j0) ( r1…rn ) )! )

En donde r1, ..., rn son las reglas de funcionamiento de la máquina. Las reglas son expresiones genéricas, por lo que siempre están activas y se realizan las acciones si se cumplen las condiciones correspondientes.

Ejemplos:

Máquina de Turing que graba la cinta con el carácter “1” desde la posición inicial a la derecha, indefinidamente:

( grabaunos = ( (b = " ") (cinta =: b★) (i = 1) ) ) ⟨( (cinta\i = "1") (i = i+1) )⟩

en donde, como se ve, no existe ninguna condición en la única regla existente y hay dos acciones: grabar "1" y avanzar una posición a la derecha.
Máquina de Turing que busca un determinado símbolo s sobre la cinta, hacia la derecha, y cuando lo encuentra se para:

( buscar = ( (i° = 1) ⟨((cinta\i = s) → ¡) (i = i+1))⟩ )! )

En este caso no es necesario definir estados ni alfabeto. Solo hay una condición y una acción.
Máquina de Turing con la tabla anterior de la MTU:

( Turing = ( // // valores iniciales // ( i = 1 ) // posición inicial del cabezal ( j = 1 ) // estado inicial ( cinta =: " "★) // cinta inicial (secuencia infinita a blancos) // // reglas // ⟨ ((est=1 → (cinta\i = a)) → ((cinta\i = c) (i = i+1) (j = 2))) ((est=2 → (cinta\i = b)) → ((cinta\i = a) (i = i−1) (j = 3))) ((est=3 → (cinta\i = c)) → ((cinta\i = b) (j = 1))) ⟩ )

En este caso, las 3 reglas tienen 2 condiciones y 3 acciones.

Primitivas semánticas utilizadas en una máquina de Turing

La máquina de Turing tiene a nivel operativo solamente 4 grados de libertad, que se corresponden con los tipos de operaciones que utiliza. Además, estas operaciones están restringidas a contextos específicos, no genéricos:

El movimiento del cabezal hacia la derecha o hacia la izquierda. Se correspondería con la operación de suma/resta, respectivamente. El contexto es el número de orden de las celdas de la cinta.
La sustitución del símbolo de la celda (a donde apunta el cabezal), por otro. También la sustitución de un estado por otro. La operación es la de sustitución. Los contextos son los símbolos de las celdas y los estados de la máquina.
Las condiciones de las reglas.
La operación es la de condición. Los contextos son el estado de la máquina y el símbolo de la cinta apuntado por el cabezal.
Examen, en todo momento, del conjunto de reglas para aplicar aquella que cumpla las condiciones.
La operación corresponde a la de expresión genérica, que se evalúa en todo momento.

Con las 4 dimensiones operativas de la máquina de Turing podemos implementar algoritmos a un nivel de abstracción muy bajo, con mucho detalle, de forma muy superficial. A medida que elevamos el nivel de abstracción, encontramos más grados de libertad y, por lo tanto, más flexibilidad y más posibilidades expresivas, tanto a nivel operativo como descriptivo.

MENTAL ofrece más grados de libertad que una máquina de Turing. En MENTAL los grados de libertad son las propias primitivas.

A nivel general (no solo operativo), en la implementación de la máquina de Turing se utilizan (explícita o implícitamente) las siguientes primitivas de MENTAL:

N°	Primitiva	Función
1	`(...)` (secuencia)	Secuencia de los elementos de la cinta (memoria lineal)
2	`+` (suma) y `−` (resta)	Desplazar respectivamente hacia la derecha y hacia la izquierda el cabezal sobre la cinta
3	`=` (sustitución)	Sustituir el símbolo en una celda de la cinta en la posición del cabezal
4	`=:` (sustitución diferida, representación)	Se utilizan indirectamente en las operaciones derivadas `★` (repetición) y `…` (rango)
5	`→` (condición)	Condición de cada regla de funcionamiento de la máquina
6	`\` (particularización cuantitativa)	Acceder a un determinado símbolo (del alfabeto o de la cinta)
7	evaluación (no hay símbolo) y `°` (no evaluación)	En las expresiones de sustitución
8	Generalización no parametrizada	En las definiciones de las reglas

Las primitivas que no se utilizan son:

Conjunto (agrupación paralela). La máquina de Turing es una máquina secuencial que utiliza una memoria secuencial.
Ejecución (comienzo y fin).
Navegación por una estructura jerárquica. La estructura de la memoria de la máquina de Turing (la cinta) es lineal.
Particularización cualitativa.
Equivalencia.
Generalización parametrizada.
Parar y continuar.

Adenda
El Entscheidungsproblem

El Entscheidungsproblem, o problema de la decidibilidad, es un problema planteado inicialmente por David Hilbert en el Congreso Internacional de Matemáticos de Paris de 1900, pero que evolucionó a una cuestión de tipo general. Se trata del problema de la decidibilidad de una proposición matemática, de saber si existe un algoritmo que permita determinar si una proposición matemática es verdadera o falsa en un sistema axiomático formal.

A este problema hubo varias respuestas:

Gödel demostró en 1931 que el problema de la decidibilidad es irresoluble con la lógica. La lógica no puede fundamentar la matemática.
Church demostró en 1935 que el problema de la decidibilidad no podía resolverse con el cálculo lambda.
Turing demostró en 1936 (en su artículo de ese año) que el problema de la parada es indecidible. No existe ningún procedimiento que permita conocer si una máquina de Turing llegará a pararse o no. La matemática no puede ser modelada o fundamentada completamente por los ordenadores.

La demostración de Turing fue aceptada por Gödel y Church como el argumento más simple y mejor.

Demostración de la indecidibilidad del problema de la parada

La demostración (por reducción al absurdo) de que este problema es indecidible es similar a la de Gödel con su teorema de incompletud:

Supongamos que exista una máquina de Turing denominada H, que tenga como entrada el código m de una máquina de Turing, H(m), y que obtiene como resultado 0 (si m no se para) o 1 (si m se para).
Entonces podemos construir otra máquina H'(m) basada en H(m): H'(m)=0 si H(m)=1 y H'(m)= 1 si H(m)=0. Llamando m' al código de H', tenemos:
- H'(m') entra en un bucle (no se para) si se para.
- H'(m') se para si entra en un bucle (si no se para).
Como esto es una contradicción, H' no puede existir y tampoco H (sobre la que se ha construido H'). Por consiguiente, no existe la función de parada; es incomputable.

La máquina de Turing universal (MTU) más simple

Un modelo computacional que simule una MTU, o tenga el mismo poder computacional que una MTU, se denomina “Turing-completo”. En teoría, puede haber muchas MTU, según el número m de estados internos y el número n de símbolos (también llamados “colores”), que se puede identificar con estos dos parámetros como MTU(m, n).

Claude Shannon [1956] fue el primero en plantear la cuestión de encontrar la MTU más pequeña posible. Demostró que 2 símbolos son suficientes sin limitación en el número de estados, o bien 2 estados sin limitaciones en el número de símbolos.

Marvin Minsky demostró en 1961 que cualquier algoritmo se puede implementar en una máquina mínima con solo 2 registros numéricos y 3 instrucciones: incrementar el valor de un registro, decrementar el valor de un registro y bifurcar a otra instrucción si el valor de un registro es cero. En 1962, Marvin Minsky encontró una MTU(7, 4) (7 estados, 4 símbolos).

Hoy sabemos que la MTU más pequeña es MTU(2, 3), es decir 2 estados y 3 símbolos. Wolfram, en su obra “A New Kind of Science” [2002], describía un autómata celular que era una MTU de 2 estados y 5 colores y conjeturaba que una MTU(2, 3) podía ser también universal. El 14 de Mayo de 2007, Wolfram anunció un premio de 25.000 $ para la primera persona que demostrase o refutase esta conjetura. El 24 de Octubre de 2007 se anunció que el premio lo había ganado Alex Smith, un estudiante de 20 años de electrónica e informática de la Universidad de Birminham. Wolfram quería demostrar cómo la complejidad emerge de los sistemas más simples.

Las extensiones de una máquina de Turing

En su tesis de 1938, Turing hacía referencia a distintos tipos de máquinas:

Las “a-machines” (máquinas automáticas), que hoy denominamos “máquinas de Turing”, que son totalmente determinísticas.
Las “c-machines” (máquinas de selección, la c indica “choice”) que añadía a las máquinas automáticas el poder de selección o decisión, por lo que eran no determinísticas:
Las “o-machines” (máquinas oráculo), máquinas que detienen su proceso en el estado “o” (de oráculo), esperando para completar la computación la decisión de “el oráculo”, una entidad no especificada “aparte de decir que no puede ser una máquina” [Turing, 1939]. Turing ideó este tipo de máquinas para demostrar que, a pesar de ser más potentes, la indecibilidad estaba todavía presente.

Las “u-machines” (máquinas desorganizadas, la "u" es de “unorganized”) para emular la mente humana.

Bibliografía

Brookshear, J. Glenn. Teoría de la Computación. Lenguajes formales, autómatas y complejidad. Addison-Wesley Iberoamericana, 1993.
Church, Alonzo. The Calculi of Lambda Conversion. Annals of Mathematicals Studies, No. 6. Princeton University Press, Princeton, New Jersey, 1941.
Davis, Martin. Universal Computer: The Road from Leibniz to Turing. W.W. Norton, 2000.
Davis, Martin. Engines of Logic: Mathematicians and the origin of the computer. W.W. Norton, 2000.
Davis, Martin. Why there is no such discipline as hypercomputation. Applied Mathematics and Computation 178 (1): 4-7, 2006. Disponible online..
Davis, Martin. The Myth of Hypercomputation. Alan Turing: Life and Legacy of a Great Thinker. Springer, 2004.
Denning, Peter J.; Metcalfe, Robert M. (eds.). Beyond Calculation: The Next Fifty Years of Computing. Copernicus Springer-Verlag, 1997.
Dyson, George. La Catedral de Turing. Debate, 2015.
Goldin, Dina; Smolka, Scott A.; Wegner, Peter (eds.). Interactive Computation: The New Paradigm. Springer, 2006.
Hodges, Andrew. Alan Turing: The Enigma. Random House, 1992.
Isaacson, Walter. Los Innovadores. Historia de los genios que crearon Internet. Debate, 2014.
Leavitt, David. Alan Turing. El hombre que sabía demasiado. Antoni Bosch Editor, 2008.
Milner, Robin. Elements of Interaction (Turing Award Lecture). Communications of the ACM 36:!, 1993. Disponible online.
Minsky, Marvin. Site and Structure of Universal Turing Machines using Tag Systems, En Recursive Function Theory, Symposium in Pure Mathematics 5: 229-238, 1962.
Shannon, Claude. A Universal Turing Machine with two Internal States. Automata Studies, Princeton University Press, pp. 157-165, 1956.
Siegelmann, Hava T. Computation Beyond the Turing Limit. Science, vol. 268, 28 Abril 1995, pp. 545-548.
Stein, Lynn Andrea. Challenging the Computational Metaphor: Implications for How We Think. Cybernetics and Systems 30 (6): 473-507, 1999.
Strathern, Paul. Turing y el ordenador. Siglo XXI de España Editores, 1999.
Turing, Alan M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2 (42): 230-265, 1936. Disponible online.
Turing, Alan M. Systems of Logic Based on Ordinals. Proceedings of the London Mathematical Society, 2 (45): 161-228, 1939. Disponible online.
Turing, Alan. Intelligent Machinery, 1939. En D.C. Ince, “Mechanical Intelligence”, North-Holland, 1992.
Wegner, Peter. Why interaction is more powerful than algorithms. Communications of the ACM 40 (5), 1997.
Wegner, Peter; Goldin, Dina. Interaction, computability, and Church’s Thesis. Internet, 1999.
Wolfram, Stephen. A New Kind of Science. Wolfram Media, 2002. Disponible online.